КРАЙНИ МНОЖЕСТВА

      Ще предполагаме за известни основните свойства на естествените числа, като под естествено число ще разбираме неотрицателно цяло число (значи ще считаме и нулата за естествено число). Множеството на естествените числа ще означаваме с N, т.е. полагаме  N={0,1,2,3,...}.  Когато k и l са две естествени числа, целочислен отрез от k до l ще наричаме множеството на онези естествени числа n, които удовлетворяват неравенствата  k Ј n Ј l ;  ще означаваме това множество с [k..l].  При  k Ј l  множеството [k..l] не е празно, защото му принадлежат поне числата (евентуално съвпадащи) k и l, а при  k > l  то очевидно е празно.
 
       За всяко естествено число n ние ще наричаме n-членна редица коя да е функция с дефиниционна област [1..n], а под членове на тази редица ще разбираме стойностите на функцията; под n-членна редица без повторения ще разбираме обратима функция с дефиниционна област [1..n].  Когато n е различно от 0 и е дадена една функция с дефиниционна област [1..n], на която стойностите за числата 1, 2, ..., n са съответно a1, a2, ..., an, ше означаваме тази функция с (a1,a2,...,an). По силата на дефинициите, които дадохме, под 0-членна редица следва да разбираме функцията, която е с празна дефиниционна област. Тази функция ще наричаме още празна редица и ще я означаваме с e.
 
       Когато A е множество (от какви да е обекти), а n е естествено число, ще казваме, че A е n-елементно (или че има n елементи), ако съществува n-членна редица без повторения, на която множеството на членовете съвпада с A. Едно множество ще наричаме крайно, ако то е n-елементно при някой избор на естественото число n.
 
       Примери. Празното множество е 0-елементно, защото е множество на членовете на празната редица, всяко множество от вида {a} е 1-елементно, понеже е множество на членовете на съответната 1-членна редица с единствен член a, всяко множество от вида {a,b}, където a и b са различни помежду си, е 2-елементно, тъй като е множество на членовете например на съответната 2-членна редица (a,b) (да отбележим, че и различната от нея 2-членна редица (b,a) има същото множество на членовете). Разбира се за всяко естествено число n целочисленият отрез [1..n] е n-елементно и следователно крайно множество - той е множество на членовете например на n-членната редица, която се получава като съпоставим на всяко число от този отрез същото това число. Множеството N обаче не е крайно - това можем да покажем например, като докажем чрез индукция относно n твърдението, че ако членовете на една n-членна редица са естествени числа, то множеството на тези членове притежава най-голям елемент или е празно.
 
       Забележка. Както може да се очаква, вярно е твърдението, че не може едно множество да бъде едновременно m-елементно и n-елементно за някои две различни естествени числа m и n. Доказателството обаче не е съвсем непосредствено и затова ще го дадем по-късно. Дотогава разбира се няма да използваме току-що изказаното твърдение в разсъжденията, които ще правим.
 
       Твърдение 1. Едно множество е 0-елементно точно тогава, когато е празно.
 
       Доказателство. Едно множество е 0-елементно точно тогава, когато то е множеството на членовете на празната редица.
 
       Твърдение 2. Нека n е произволно естествено число. Едно множество е n+1-елементно точно тогава, когато може да се получи от някое n-елементно множество чрез добавяне на един елемент, непринадлежащ на него.
 
       Доказателство. Ако A e n+1-елементно множество, то A е множество на членовете на някоя n+1-членна редица без повторения (a1,a2,...,an,an+1), а при това положение A=BИ{an+1}, където B е множеството на членовете на n-членната редица (a1,a2,...,an) - очевидно тя е без повторения, а an+1 не принадлежи на B. Обратно, нека A=BИ{c}, където B е n-елементно множество и c не принадлежи на B. Тогава B е множество на членовете на някоя n-членна редица без повторения (b1,b2,...,bn), а при това положение A е множеството на членовете на n+1-членната редица (b1,b2,...,bn,c) и тя е без повторения.
 
       Твърдение 3. Когато n е естествено число и е дадена една произволна n-членна редица, множеството на нейните членове е m-елементно за някое естествено число m, ненадминаващо n.
 
       Доказателство. Използваме индукция относно n. При n=0 верността на твърдението е тривиална. Предполагайки, че твърдението е вярно за дадена стойност на n, да разгледаме произволна n+1-членна редица (a1,a2,...,an,an+1). Направеното предположение позволява да твърдим, че множеството на членовете на n-членната редица (a1,a2,...,an) е m-елементно за някое естествено число m, ненадминаващо n. Обаче множеството на членовете на дадената n+1-членна редица или съвпада с току-що споменатото множество или се получава от него чрез добавяне на един елемент, непринадлежащ на него. Оттук, като използваме и твърдение 2, получаваме, че множеството на членовете на дадената редица е m-елементно или m+1-елементно. При това положение достатъчно е да отбележим, че m < m+1 Ј n+1.
 
       Твърдение 4. При произволен избор на естествено число n, ако A е n-елементно множество, то всяко негово подмножество съвпада с A или е m-елементно за някое естествено число m, по-малко от n.
 
       Доказателство. Използваме пак индукция относно n. При n=0 верността на твърдението следва от твърдение 1 и от обстоятелството, че единственото подмножество на празното множество е самото то. Предполагайки, че твърдението е вярно за дадена стойност на n, да разгледаме произволно n+1-елементно множество A и някое негово подмножество X. По твърдение 2 имаме равенство от вида A=BИ{c}, където B е n-елементно множество и c не принадлежи на B. Ако c не принадлежи на X, то X е подмножество на B и поради това е m-елементно за някое естествено число m, ненадминаващо n и следователно по-малко от n+1 (така стоят нещата и когато X съвпада с B, и когато X е m-елементно за някое естествено число m, по-малко от n). Да разгледаме сега случая, когато c принадлежи на X. Тогава X=(X\{c})И{c}. Като подмножество на B множеството X\{c} съвпада с B или е m-елементно за някое естествено число m, по-малко от n. Оттук и от написаното преди малко равенство получаваме с помощта на твърдение 2 заключението, че X съвпада с A или е m+1-елементно за някое естествено число m, по-малко от n. Оства само да отбележим, че във втория случай числото m+1 е по-малко от n+1.
 
       Твърдение 5. Ако A е k-елементно множество, B е l-елементно множество и тези две множества нямат общи елементи, то множеството AИB е k+l-елементно.
 
       Доказателство (първи начин). Нека A е множество на членовете на k-членна редица без повторения (a1,a2,...,ak), а B е множество на членовете на l-членна редица без повторения (b1,b2,...,bl). Тогава AИB е множество на членовете на k+l-членната редица
            (a1,a2,...,ak,b1,b2,...,bl)
(точното описание на тази редица е следното: това е функцията, която има за дефиниционна област целочисления отрез [1..k+l] и на произволно число i от него съпоставя ai, когато i не надминава k, и съпоставя bi-k при i > k). Понеже A и B нямат общи елементи, тя също е без повторения.
 
       Доказателство (втори начин). Ще използваме индукция относно l. Ако l е 0, то твърдението, че AИB е k+l-елементно, следва веднага от твърдение 1 и равенствата AИЖ=A, k+0=k. Да предположим сега, че това, което доказваме, е вярно за дадена стойност на l и са дадени k-елементно множество A и l+1-елементно множество B, които нямат общи елементи. По твърдение 2 имаме равенство от вида B=CИ{d}, където C е l-елементно множество и d не принадлежи на C. Тогава имаме и равенството
            AИB=(AИC)И{d},
като при това A и C нямат общи елементи, а d не принадлежи на AИC. Оттук получаваме последователно, че множеството AИC е k+l-елементно, а множеството A е (k+l)+1-елементно. Благодарение на равенството (k+l)+1=k+(l+1) с това целта ни е постигната.
 
       Твърдение 6. Обединението на всеки две крайни множества е крайно.
 
       Доказателство. Нека A е k-елементно множество, а B е l-елементно множество. Имаме равенството
            AИB=AИ(B\A)
и очевидно множествата A и B\A нямат общи елементи. По твърдение 4 второто от тези множества е m-елементно за някое m, не надминаващо l. Оттук по твърдение 5 получаваме, че множеството AИB е k+m-елементно.
 
       Твърдение 7. Ако всички елементи на едно крайно множество са крайни множества, то тяхното обединение също е крайно множество.
 
       Доказателство. Чрез индукция относно естественото число n ще докажем твърдението, че когато всички елементи на едно n-елементно множество са крайни множества, тяхното обединение също е крайно множество. При n=0 това е така, защото в този случай въпросното обединение е празно. Да предположим сега, че това, което доказваме, е вярно за дадена стойност на n и е дадено едно n+1-елементно множество K, на което всички елементи са крайни множества. По твърдение 2 имаме равенство от вида K=LИ{B}, където L е някое n-елементно множество и B не принадлежи на L. Ясно е, че всички елементи на L са крайни множества и следователно (понеже L е n-елементно) тяхното обединение също е крайно. Да означим това обединение с A. Понеже и B е крайно множество, твърдение 6 позволява да заключим, че обединението на A и B също е крайно множество, а то очевидно е обединението на всички елементи на K.

Последно изменение: 11.10.2002 г.